<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Document</title>
</head>
<body>
	<script>
		// 菲波拉契数列(兔子数列)
		// 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .....
		// 如 求解该数列第15项？

		/*console.log("第1项为：1")
		console.log("第2项为：1")

		var a = 1, b = 1;
		var r;

		for (var i = 3; i <= 15; i++) {
			r = a + b;
			console.log("第"+ i +"项：" + r);
			// 更新a,b
			a = b;
			b = r;
		}*/

		/*// 第三项
		r = a + b;
		console.log("第3项：" + r);
		// 更新a,b
		a = b;
		b = r;

		// 第四项
		r = a + b;
		console.log("第4项：" + r);
		// 更新a,b
		a = b;
		b = r;

		// 第五项
		r = a + b;
		console.log("第5项：" + r);
		// 更新a,b
		a = b;
		b = r;

		// 第六项
		r = a + b;
		console.log("第6项：" + r);
		// 更新a,b
		a = b;
		b = r;*/
	</script>

	<script>
		// 定义函数，求菲波拉契数列
		function fn(n) {
			if (n <= 2)
				return 1;
			var a = 1, b = 1, r;
			for (var i = 3; i <= n; i++) {
				r = a + b;
				a = b;
				b = r;
			}
			return r;
		}
		console.log("循环：")
		console.time();
		console.log(fn(20))
		console.timeEnd();
	</script>

	<script>
		// fn(10) === fn(9) + fn(8)
		// fn(9) === fn(8) + fn(7)

		/*var fn = function(n){
			if (n <= 2)
				return 1;
			else
				return fn(n-1) + fn(n-2);
		}*/

		var count = 0;

		var fn = function(n) {
			count++;
			return n <= 2 ? 1 : fn(n-1) + fn(n-2);
		}

		console.log("递归：")
		console.time();
		console.log(fn(30))
		console.timeEnd();
		console.log("次数：" + count)
	</script>
</body>
</html>